package test230530;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/30 18:58
 * 91. 解码方法
 * https://leetcode.cn/problems/decode-ways/
 */
@SuppressWarnings({"all"})
public class Solution01 {
    public int numDecodings(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        // dp[i] 表示以第 i 个字符为结尾的解码方法总数
        int[] dp = new int[n];
        if (chars[0] != '0') dp[0] = 1;  // 初始化第一个位置, 即单个字符能进行编码时
        if (n <= 1) {
            return dp[0];  // 处理边界
        }
        if (chars[1] != '0' && chars[0] != '0') dp[1] += 1; // 以 1 位置为结尾且该位置可以进行编码
        int t = (chars[0] - '0') * 10 + (chars[1] - '0');
        if (t >= 10 && t <= 26) dp[1] += 1;
        // 动态规划过程
        for (int i = 2; i < n; ++i) {
            if (chars[i] != '0') {
                // i 位置单个字符能够进行编码的情况
                dp[i] += dp[i-1];
            }
            t = (chars[i-1] - '0') * 10 + (chars[i] - '0');
            if (t >= 10 && t <= 26) dp[i] += dp[i-2];
        }
        return dp[n-1];
    }
}
